//给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。 
//
// 示例: 
//
// 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
//输出: [3,3,5,5,6,7] 
//解释: 
//
//  滑动窗口的位置                最大值
//---------------               -----
//[1  3  -1] -3  5  3  6  7       3
// 1 [3  -1  -3] 5  3  6  7       3
// 1  3 [-1  -3  5] 3  6  7       5
// 1  3  -1 [-3  5  3] 6  7       5
// 1  3  -1  -3 [5  3  6] 7       6
// 1  3  -1  -3  5 [3  6  7]      7 
//
// 
//
// 提示： 
//
// 你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。 
//
// 注意：本题与主站 239 题相同：https://leetcode-cn.com/problems/sliding-window-maximum/ 
// Related Topics 队列 滑动窗口 单调队列 堆（优先队列） 👍 439 👎 0

package leetcode.editor.offer;

import java.util.Deque;
import java.util.LinkedList;

// 59. 滑动窗口的最大值
class HuaDongChuangKouDeZuiDaZhiLcof {
    public static void main(String[] args) {
        Solution solution = new HuaDongChuangKouDeZuiDaZhiLcof().new Solution();
        solution.maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums.length == 0) {
                return nums;
            }

            int num = 0;
            int[] res = new int[nums.length - k + 1];
            MyQueue queue = new MyQueue();
            // 先将第一个窗口的元素入队
            for (int i = 0; i < k; i++) {
                queue.push(nums[i]);
            }
            // 第一个窗口的最大值
            res[num++] = queue.peek();

            for (int i = k; i < nums.length; i++) {
                // 移动前先将左边出栈
                queue.poll(nums[i - k]);
                // 再将下一个元素入栈
                queue.push(nums[i]);
                // 在获取移动后的这个窗口的最大值
                res[num++] = queue.peek();
            }

            return res;

        }

        class MyQueue {
            Deque<Integer> deque = new LinkedList<>();

            //弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出
            //同时判断队列当前是否为空
            void poll(int val) {
                if (!deque.isEmpty() && val == deque.peek()) {
                    deque.poll();
                }
            }

            //添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出
            //保证队列元素单调递减
            //比如此时队列元素3,1，2将要入队，比1大，所以1弹出，此时队列：3,2
            void push(int val) {
                while (!deque.isEmpty() && val > deque.getLast()) {
                    deque.removeLast();
                }
                deque.add(val);
            }

            //队列队顶元素始终为最大值
            int peek() {
                return deque.peek();
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
